#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define NAMESIZE 20
#define TRUE 1
#define FALSE 0
#define EqualFun strcmp
#define SetValue strcpy
typedef char NODE[NAMESIZE];
struct BROTHERNODE				
{//兄弟节点类型，表示兄弟节点
    NODE node;					//兄弟节点名称 
    struct BROTHERNODE *next;	//兄弟节点链接指针，链接其他兄弟
};
typedef struct BROTHERNODE *BROTHER;
struct PARENTNODE				
{//双亲节点类型，表示子树根节点 
    NODE node;					//双亲节点名称 
    BROTHER children;			//所有子节点 
};
typedef struct PARENTNODE PARENT;	//重命名双亲节点类型
struct TREENODE				
{//树分支节点类型 
    PARENT node;
    struct TREENODE *next;
};
typedef struct TREENODE *TREE;				//双亲节点，表示子树的树根节点 


int Equal(NODE n1, NODE n2, int (*fun)()) 
{
    return (int)fun(n1, n2);
}

void Set(NODE n1, NODE n2, char *(fun)())
{
    fun(n1, n2);
}

BROTHER AddABrother(BROTHER br, NODE node)  	
{//在br兄弟节点群中增加一个兄弟节点node
    BROTHER b, pb;					//兄弟节点变量 
    b = (BROTHER)malloc(sizeof(struct BROTHERNODE));	//动态开辟一个兄弟单元 
    b->next = NULL;
    Set(b->node, node, SetValue);					//本例中与strcpy(b->node, node);等价 
    if (br == NULL)							//没有兄弟节点的情况 
        br = b;
    else									//有兄弟节点的情况 
    {
        pb = br;
        while (pb -> next) pb = pb -> next;
        pb -> next = b;
    }
    return br;								//返回兄弟节点 
}

TREE Form_Pa_Ch(NODE pa, BROTHER br) 
{//双亲节点与兄弟节点构成子树
    TREE parent;
    parent = (TREE)malloc(sizeof(struct TREENODE));//创建双亲节点 
    Set(parent->node.node, pa, SetValue);
    parent->node.children=br;//兄弟节点与双亲节点构成子树 
    parent->next=NULL;
    return parent;								//返回带兄弟节点的双亲节点，即子树
}

TREE AddAsubTree(TREE tree, TREE subtree)	
{//双亲节点加入到树中 
    TREE t =tree;			//临时树 
    if(tree == NULL)		//树不存在 
        tree = subtree;		//带子节点的双亲节点即为树 
    else                    //树存在 
    {
        while (t->next) t = t->next;
        t->next = subtree;	//带子节点的双亲节点加入到树的最后
    }
    return tree;			//返回树指针 
}

BROTHER ClearBrothers(BROTHER br)	
{//回收兄弟节点空间 
    BROTHER br1 = br;				//临时兄弟变量 
    while (br)
    {
        br1 = br;
        br = br->next;
        free(br1);					//回收单元 
    }
    return br;						//返回NULL 
}

TREE ClearTree(TREE tree)			//回收树空间 
{
    TREE tree1 = tree;				//临时树 
    while (tree)
    {
        tree1 = tree;
        tree = tree->next;
        free(tree1);				//回收单元 
    }
    return tree;					//返回NULL
}

void CreateStr(char *brotherset)	//字符数组转换为多个字符串 
{
    char *c = brotherset;				//临时字符串 
    while (*c)
    {
        if(*c == '/') *c = '\0';				//插入字符串结束标记 
        c++;
    }
    c++;
    *c = '\0';						//多一个结束标记 
}

BROTHER CreateBrothers(BROTHER brothers, char *brotherset)
{                                                   //若干个节点构成兄弟 
    char *p = brotherset;							//多个节点，分隔符'/' 
    NODE node;
    CreateStr(brotherset);							//变为多个字符串 
    while (*p)
    {//与strcpy(node, p);等价，读取节点 
        Set(node, p, SetValue);
        brothers = AddABrother(brothers, node);		//加入兄弟关系中 
        p += strlen(node) + 1;
    }
    return brothers;								//返回兄弟节点链表 
}

TREE CreateTree(TREE tree, char *filename)	//从文件创建树 
{
    TREE subtree;
    BROTHER brothers;
    FILE *fp;
    char parent[200], brotherset[5000];
    fp = fopen(filename, "r");
    while (!feof(fp))							//文件中是否还存在树的节点名称 
    {
        fscanf(fp, "%s", parent);				//读入双亲节点 
        fscanf(fp, "%s", brotherset);
        brothers = NULL;					//读入若干兄弟节点（子节点），分隔符'/' 
        brothers = CreateBrothers(brothers, brotherset);		//构建双亲节点 
        subtree = Form_Pa_Ch(parent, brothers);				//构建子树 
        tree = AddAsubTree(tree, subtree);					//树中加入子树
    }
    fclose(fp);
    return tree; 
}

void main(int argc, char const *argv[])
{//建树
    TREE tree = NULL;                                       //链式存储结构树 
    char *filename="tree.txt";                              //树数据文件
    tree = CreateTree(tree, filename);                      //创建链式存储结构树
    printf("\n建树成功!\n");
    ClearTree(tree);                                        //回收树空间
}
